import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Merge {
    // leetcode 合并区间
    // https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
        });
        int start = intervals[0][0], end = intervals[0][1];
        List<int[]> ret = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= end) {
                if (intervals[i][1] > end) {
                    end = intervals[i][1];
                }
            }else {
                ret.add(new int[]{start,end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        ret.add(new int[]{start,end});
        return ret.toArray(new int[][]{});
    }
}
